UVa/924 - Spreading the news/924.cpp

   1 /*
   2   Problem: 924 - Spreading the news (UVa Online Judge)
   3   Andrés Mejía-Posada
   4
   5   Verdict: Wrong answer
   6  */
   7 #include <iostream>
   8 #include <queue>
   9 #include <vector>
  10
  11 using namespace std;
  12
  13 int main(){
  14   int E;
  15   scanf("%d", &E);
  16   vector<int> g[E];
  17   for (int i=0; i<E; ++i){
  18     int N;
  19     scanf("%d", &N);
  20     while (N--){
  21       int j;
  22       scanf("%d", &j);
  23       g[i].push_back(j);
  24     }
  25   }
  26
  27   int T;
  28   scanf("%d", &T);
  29   while (T--){
  30     int u;
  31     scanf("%d", &u);
  32     if (g[u].size() == 0){
  33       printf("0\n");
  34     }else{
  35       int max_boom = 0, first_day = 0, booms[E];
  36       bool visited[E];
  37       memset(booms, 0, sizeof booms);
  38       memset(visited, false, sizeof visited);
  39       queue<pair<int, int> > q;
  40       q.push(make_pair(u, 0));
  41       while (q.size()){
  42         int person = q.front().first;
  43         int today = q.front().second;
  44         q.pop();
  45
  46         if (visited[person]) continue;
  47
  48         visited[person] = true;
  49         booms[today]++;
  50         if (booms[today] > max_boom){
  51           max_boom = booms[today];
  52           first_day = today;
  53         }
  54
  55         vector<int> &friends = g[person];
  56         for (int i=0; i<friends.size(); ++i){
  57           if (!visited[friends[i]]){
  58             q.push(make_pair(friends[i], today + 1));
  59           }
  60         }
  61       }
  62       printf("%d %d\n", max_boom, first_day);
  63     }
  64   }
  65   return 0;
  66 }